package com.zp.self.module.level_4_算法练习.算法.动态规划;

/**
 * @author By ZengPeng
 */
public class 力扣_64_最小路径和 {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_64_最小路径和().minPathSum(new int[][]{{1,3,1},{1,5,1},{4,2,1}}));
        System.out.println(new 力扣_64_最小路径和().minPathSum(new int[][]{{1,2,3},{4,5,6}}));
        System.out.println(new 力扣_64_最小路径和().minPathSum(new int[][]{{1},{1}}));
        System.out.println(new 力扣_64_最小路径和().minPathSum(new int[][]{{1}}));
    }

    /**
    题目：给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，
     使得路径上的数字总和为最小。
     说明：每次只能向下或者向右移动一步。

     示例 1：
     输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
     输出：7
     解释：因为路径 1→3→1→1→1 的总和最小。

     示例 2：
     输入：grid = [[1,2,3],[4,5,6]]
     输出：12

    分析：【perfect】应属简单题了，这个是最金典的动态规划
       1.动态规划 : f[m,n] = min ( f[m-1,n], f[m-1,n] )  --执行用时：2 ms, 在所有 Java 提交中击败了95.10%的用户
       2.此处应该不能用贪心算法吧，目光短浅，看不到后续的更优解

    边界值 & 注意点：
       1.
     **/
    public int minPathSum(int[][] grid) {
        for (int i = 1; i < grid[0].length; i++)
            grid[0][i]+=grid[0][i-1];
        for (int i = 1; i < grid.length; i++)
            grid[i][0]+=grid[i-1][0];

        for (int i = 1; i < grid.length; i++) {
            for (int j = 1; j < grid[0].length; j++) {
                 grid[i][j]  += Math.min(grid[i-1][j],grid[i][j-1]);
            }
        }
        return grid[grid.length-1][grid[0].length-1];
    }
}
